package main

import (
	"fmt"
	common "leetcode/tree/common"
	"strings"
)

func binaryTreePaths(root *common.TreeNode) []string {
	if root == nil {
		return nil
	}
	var res []string
	dfs(root, []string{}, &res)
	return res
}

func dfs(node *common.TreeNode, path []string, res *[]string) {
	if node.Left == nil && node.Right == nil {
		*res = append(*res, strings.Join(append(path, fmt.Sprintf("%d", node.Val)), "->"))
		return
	}
	path = append(path, fmt.Sprintf("%d", node.Val))
	if node.Left != nil {
		dfs(node.Left, path, res)
	}
	if node.Right != nil {
		dfs(node.Right, path, res)
	}
}

func bfs(root *common.TreeNode) (paths []string) {
	type data struct {
		node *common.TreeNode
		path []string
	}
	var queue []data
	queue = append(queue, data{node: root, path: []string{fmt.Sprintf("%d", root.Val)}})
	for len(queue) != 0 {
		size := len(queue)
		for i := 0; i < size; i++ {
			head := queue[0]
			queue = queue[1:]

			if head.node.Left == nil && head.node.Right == nil {
				paths = append(paths, strings.Join(head.path, "->"))
				continue
			}
			if head.node.Left != nil {
				queue = append(queue, data{node: head.node.Left, path: append(head.path, fmt.Sprintf("%d", head.node.Left.Val))})
			}
			if head.node.Right != nil {
				queue = append(queue, data{node: head.node.Right, path: append(head.path, fmt.Sprintf("%d", head.node.Right.Val))})
			}
		}
	}
	return
}

func main() {
	root := common.TreeNode{Val: 1}
	node2 := common.TreeNode{Val: 2}
	node3 := common.TreeNode{Val: 3}
	node5 := common.TreeNode{Val: 5}
	root.Left = &node2
	root.Right = &node3
	node2.Right = &node5
	fmt.Println(binaryTreePaths(&root))

	fmt.Println(bfs(&root))
}
